//
// Created by zx208 on 2024/11/2.
//

#include "LinkedQueue_BinaryTree.h"

Status InitQueue(LinkedQueue *Q){
    Q->front = Q->rear = (QueueNode *)malloc(sizeof(QueueNode));
    if(!Q->front) exit(OVERFLOW);

    Q->front->next = NULL; //使该节点next域为NULL
    return OK;
}

Status Entry_LQ(LinkedQueue *Q, BiTree e){
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
    if (!p) exit(OVERFLOW);
    p->data = *e;
    p->next = NULL;
    Q->rear->next = p; // 将新元素接到队尾
    Q->rear = p; // 修改队尾指针
    return OK;
}

Status Out_LQ(LinkedQueue *Q, BiTree e){
    if (Q->front == Q->rear) return ERROR;
    QueueNode *pfree = Q->front->next;
    *e = pfree->data;
    Q->front->next = pfree->next;
    // 特殊情况 当元素出队后发现队列中没有元素时，将尾指针修改成头指针
    if (Q->rear == pfree)
        Q->rear = Q->front;
    free(pfree);
    return OK;
}

Status IsEmpty(LinkedQueue *Q){
    return Q->front == Q->rear;
}

// 使用先序遍历创建二叉树
void Create_BiTree_Pre(BiTree *T){
    char e;
    scanf(" %c", &e);
    if(e == '#') *T = NULL;
    else {
        *T = (BiTree) malloc(sizeof(  BiNode));
        (*T)->data = e;
        Create_BiTree_Pre(&(*T)->lchild);
        Create_BiTree_Pre(&(*T)->rchild);
    }
}

// 层序遍历
void LevelOrder_unrec(BiTree T){
    LinkedQueue Q;
    BiTree p = (BiTree) malloc(sizeof( BiNode));
    InitQueue(&Q);
    Entry_LQ(&Q, T);
    while(!IsEmpty(&Q)){
        Out_LQ(&Q, p);
        printf("%c ", p->data);
        if(p->lchild != NULL) Entry_LQ(&Q, p->lchild);
        if(p->rchild != NULL) Entry_LQ(&Q, p->rchild);
    }
}

int main(void){
    BiTree T = NULL;
    Create_BiTree_Pre(&T);
    LevelOrder_unrec(T);
    return 0;
}

// CDNK##J##BZ###FL##M##